// **************************************************
// *  CHOCO: an open-source Constraint Programming  *
// *     System for Research and Education          *
// *                                                *
// *    contributors listed in choco.Entity.java    *
// *           Copyright (C) F. Laburthe, 1999-2006 *
// **************************************************
package choco.integer.var;

import choco.mem.IEnvironment;
import choco.mem.IStateInt;
import choco.util.DisposableIntIterator;
import choco.util.IntIterator;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class CleverIntervalDomain extends AbstractIntDomain {
    protected final List<IntervalIntDomain> boundsVector = new ArrayList();


    /**
     * A random generator for random value from the domain
     */

    public static Random random = new Random(System.currentTimeMillis());

    private IntervalIntDomain idtmp;
    private IntervalIntDomain idtmp2;


    protected IStateInt vectorSize;

    protected IStateInt size;
    /**
     * The backtrackable minimal value of the variable.
     */

    protected int i;

    protected IStateInt inf;

    /**
     * The backtrackable maximal value of the variable.
     */

    protected IStateInt sup;

    public CleverIntervalDomain(IntDomainVarImpl v, int a, int b) {
        variable = v;
        problem = v.getProblem();
        IEnvironment env = problem.getEnvironment();
        boundsVector.add(0, new IntervalIntDomain(v, a, b));
        vectorSize = env.makeInt(1);
        size = env.makeInt(b - a + 1);
        inf = env.makeInt(a);
        sup = env.makeInt(b);
    }


    /**
     * Check if it contains <code>x</code>
     *
     * @param x the value to check
     * @return true if it contains x, false else.
     */
    public boolean contains(int x) {
        if (x < getInf() || x > getSup()) {
            return false;
        }
        i = searchSubDom(x);
        while (i > -1 && i < vectorSize.get()) {
            idtmp = boundsVector.get(i);
            if (x < idtmp.getInf()) {
                return false;
            }
            if (x <= idtmp.getSup()) {
                return true;
            }
            if (x > idtmp.getSup()) {
                i++;
            }
        }
        return false;
    }

    /**
     * Return the value of the following <code>x</code>
     *
     * @param x the previous value
     * @return the value that follows <code>x</code>
     */
    public int getNextValue(int x) {
        if (x < getInf()) {
            return getInf();
        }
        if (x < getSup()) {
            i = searchSubDom(x);
            i=(i>-1?i:0);
            while (i < vectorSize.get()) {
                idtmp = boundsVector.get(i);
                if (x < idtmp.getInf()) {
                    return idtmp.getInf();
                }
                if (x < idtmp.getSup()) {
                    return x + 1;
                }
                if (x >= idtmp.getSup()) {
                    i++;
                }
            }
        }
        return Integer.MAX_VALUE;
    }

    /**
     * Return the value of the previous <code>x</code>
     *
     * @param x the following value
     * @return the value that previous <code>x</code>
     */
    public int getPrevValue(int x) {
        if (x > getSup()) {
            return getSup();
        }
        if (x > getInf()) {
            i = searchSubDom(x);
            i=(i>-1?i:vectorSize.get()-1);
            while (i > -1) {
                idtmp = boundsVector.get(i);
                if (x > idtmp.getSup()) {
                    return idtmp.getSup();
                }
                if (x > idtmp.getInf()) {
                    return x - 1;
                }
                if (x <= idtmp.getInf()) {
                    i--;
                }
            }
        }
        return Integer.MIN_VALUE;
    }

    /**
     * return a random value
     *
     * @return a randomize value
     */
    public int getRandomValue() {
        if (size.get() == 1) return getInf();
        if (vectorSize.get() == 1) return boundsVector.get(0).getRandomValue();
        int vec = random.nextInt(vectorSize.get());
        return boundsVector.get(vec).getRandomValue();
    }

    /**
     * Return the size of the domain
     *
     * @return the size of the domain
     */
    public int getSize() {
        return size.get();
    }


    /**
     * Return the size of the vector domain
     *
     * @return the size of the vector domain
     */
    public int getVectorSize() {
        return vectorSize.get();
    }

    /**
     * Check if there is a next value in the domain
     *
     * @param x the last value
     * @return wether there is a next value
     */
    public boolean hasNextValue(int x) {
        return (x < getSup());
    }

    /**
     * Check if there is a previous value in the domain
     *
     * @param x the last value
     * @return wether there is a previous value
     */
    public boolean hasPrevValue(int x) {
        return (x > getInf());
    }

    public DisposableIntIterator getIterator() {
        return new DisposableIntIterator() {
            int x = getInf() - 1;

            public boolean hasNext() {
                return x < getSup();
            }

            public int next() {
                return ++x;
            }

            public void remove() {
                throw new UnsupportedOperationException();
            }

            public void dispose() {
            }
        };
    }

    private int searchSubDom(int val) {
        int idxVect = 0;
        int binf = 0;
        int bsup = vectorSize.get();
        int delta;
        boolean trouve = false;
        boolean trouvable = true;

        while (trouvable && !trouve) {
            delta = ((bsup + binf) / 2) - idxVect;
            idxVect = idxVect + delta;
            idtmp2 = boundsVector.get(idxVect);
            int i =  idtmp2.getInf();
            int s =  idtmp2.getSup();
            if (val >=  i && val <= s) {
                trouve = true;
                continue;
            } else {
                if (delta == 0) {
                    trouvable = false;
                    continue;
                }
                if (val < i) {
                    bsup = idxVect;
                    continue;
                }
                if (val > s) {
                    binf = idxVect;
                    continue;
                }
            }
        }
        if (!trouvable) {
            idxVect = -1;
        }
        return idxVect;
    }

    /**
     * Remove <code>x</code> from the domain
     *
     * @param x to remove
     * @return wether the value has been removed
     */
    public boolean remove(int x) {
        i = searchSubDom(x);
        if (i > -1) {
            idtmp = boundsVector.get(i);
            if (x < idtmp.getInf() || x > idtmp.getSup()) {
                return false;
            }
            if (idtmp.getSize() == 1) {
                boundsVector.remove(i);
                vectorSize.add(-1);
                size.add(-idtmp.getSize());
                if (i == 0) {
                    inf.set(this.getNextValue(inf.get()));
                    //System.out.println("MàJ de binf : " + x + "=>" + inf.get());
                }
                if (i == vectorSize.get()) {
                    sup.set(this.getPrevValue(sup.get()));
                    //System.out.println("MàJ de bsup : " + x + "=>" + sup.get());
                }
                return true;
            }
            if (x == idtmp.getInf()) {
                updateInf(x + 1, idtmp);
                if (i == 0) {
                    inf.set(this.getNextValue(inf.get()));
                    //System.out.println("MàJ de binf : " + x + "=>" + inf.get());
                }
                return true;
            }
            if (x == idtmp.getSup()) {
                updateSup(x - 1, idtmp);
                if (i == vectorSize.get() - 1) {
                    sup.set(this.getPrevValue(sup.get()));
                    //System.out.println("MàJ de bsup : " + x + "=>" + sup.get());
                }
                return true;
            }
            if (idtmp.getSize() > 2) {
                IntervalIntDomain newId = new IntervalIntDomain(variable, x + 1, idtmp.getSup());
                idtmp.updateSup(x - 1);
                boundsVector.add(i + 1, newId);
                vectorSize.add(+1);
                size.add(-1);
                return true;
            }
        }
        return false;
    }

    /**
     * Return the upper bound
     *
     * @return the upper bound
     */
    public int getSup() {
        return sup.get();
    }

    /**
     * Return the lower bound
     *
     * @return the lower bound
     */
    public int getInf() {
        return inf.get();
    }

    /**
     * Restict the domain to <code>x</code>.
     *
     * @param x
     */
    public void restrict(int x) {
        boundsVector.clear();
        boundsVector.add(0, new IntervalIntDomain(variable, x, x));
        inf.set(x);
        sup.set(x);
        size.set(1);
        vectorSize.set(1);
    }

    /**
     * Remove an specific element from the vector
     *
     * @param idx the index of the sub domain to remove
     * @param id  the sub domain
     */
    private void removeElement(int idx, IntervalIntDomain id) {
        boundsVector.remove(0);
        vectorSize.add(-1);
        size.add(-id.getSize());
    }

    /**
     * Update the lower boudn of a specific sub domain to x
     *
     * @param x  the new lower bound of the sub domain
     * @param id the sub interval
     */
    private void updateInf(int x, IntervalIntDomain id) {
        int k = id.getInf();
        id.updateInf(x);
        size.add(k - id.getInf());
    }

    /**
     * Update the upepr bound of a specific sub domain to x
     *
     * @param x  the new lower bound of the sub domain
     * @param id the sub interval
     */
    private void updateSup(int x, IntervalIntDomain id) {
        int k = id.getSup();
        id.updateSup(x);
        size.add(id.getSup() - k);
    }

    /**
     * Update the lower bound
     *
     * @param x the new lower bound
     * @return the new lower bound
     */
    public int updateInf(int x) {
        boolean uptodate = false;
        while (!uptodate) {
            idtmp = boundsVector.get(0);
            if (x > idtmp.getSup()) {
                removeElement(0, idtmp);
                continue;
            }
            if (x > idtmp.getInf()) {
                updateInf(x, idtmp);
                inf.set(x);
                uptodate = true;
            }
        }
        return x;
    }

    /**
     * Update the upper bound
     *
     * @param x the new upper bound
     * @return the new upper bound
     */
    public int updateSup(int x) {
        boolean uptodate = false;
        while (!uptodate) {
            idtmp = boundsVector.get(vectorSize.get()-1);
            if (x < idtmp.getInf()) {
                removeElement(vectorSize.get() - 1, idtmp);
                continue;
            }
            if (x < idtmp.getSup()) {
                updateSup(x, idtmp);
                sup.set(x);
                uptodate = true;
            }
        }
        return x;
    }

    public boolean isEnumerated() {
        return true;
    }

    public boolean isBoolean() {
        return false;
    }

    public IntIterator getDeltaIterator() {
        return null;
    }

    /**
     * Pretty print of the domain
     *
     * @return a pretty print of the domain
     */
    @Override
    public String pretty() {
        StringBuffer st = new StringBuffer("[");
        for (IntervalIntDomain aBoundsVector : boundsVector) {
            st.append(aBoundsVector.pretty());
        }
        st.append("]");
        return st.toString();
    }

}